home *** CD-ROM | disk | FTP | other *** search
/ Visual Basic Source Code / Visual Basic Source Code.iso / vbsource / vbdatabs / rbtreeb.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1999-03-14  |  10.2 KB  |  336 lines
  1. // ------------------------------- //
  2. // -------- Start of File -------- //
  3. // ------------------------------- //
  4. // ----------------------------------------------------------- // 
  5. // C++ Source Code File Name: rbtreeb.cpp
  6. // Compiler Used: MSVC40, DJGPP 2.7.2.1, GCC 2.7.2.1, HP CPP 10.24
  7. // Produced By: Doug Gaer 
  8. // File Creation Date: 01/23/1997 
  9. // Date Last Modified: 03/15/1999
  10. // Copyright (c) 1997 Douglas M. Gaer
  11. // ----------------------------------------------------------- // 
  12. // ------------- Program Description and Details ------------- // 
  13. // ----------------------------------------------------------- // 
  14. /*
  15. The VBD C++ classes are copyright (c) 1997, by Douglas M. Gaer.
  16. All those who put this code or its derivatives in a commercial
  17. product MUST mention this copyright in their documentation for
  18. users of the products in which this code or its derivative
  19. classes are used. Otherwise, you have the freedom to redistribute
  20. verbatim copies of this source code, adapt it to your specific
  21. needs, or improve the code and release your improvements to the
  22. public provided that the modified files carry prominent notices
  23. stating that you changed the files and the date of any change.
  24.  
  25. THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND.
  26. THE ENTIRE RISK OF THE QUALITY AND PERFORMANCE OF THIS SOFTWARE
  27. IS WITH YOU. SHOULD ANY ELEMENT OF THIS SOFTWARE PROVE DEFECTIVE,
  28. YOU WILL ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR, OR
  29. CORRECTION.
  30.  
  31. (R)ed (B)lack (T)ree node data independent functions. 
  32. */
  33. // ----------------------------------------------------------- //   
  34. #include "rbtreeb.h"
  35. #include "rbtree.h"
  36.  
  37. // Convenience macros
  38. #define T  (pp.t)  // The current node
  39. #define P  (pp.p)  // Parent 
  40. #define G  (pp.g)  // Grandparent 
  41. #define GG (pp.gg) // Great Grandparent
  42. #define S  (pp.s)  // Sibling 
  43. #define RS (pp.rs) // Right children of s 
  44. #define LS (pp.ls) // Left children of s
  45. #define M  (pp.m)  // Matching node 
  46. #define PM (pp.pm) // Parent of matching node
  47.  
  48. RBNodeBase *InsBalance(RBNodeBase *Root, PtrPack &pp)
  49. // Balance adjusting for top down insertions. Eliminates
  50. // both P and T from being red by doing rotations and
  51. // color changes. G, P, and T assumed not null coming in. 
  52. // GG may be null. At the end of this routine, only Tree 
  53. // and P will be valid with each other. G and GG may 
  54. // not reflect the proper ordering.
  55. {
  56.   RBNodeBase *cofgg; // New child of great-grandparent
  57.   int side;
  58.  
  59.   side = GG && GG->Right == G;
  60.  
  61.   if (G->Left == P) {
  62.      if (P->Right == T) { // Do double rotate
  63.         G->Left = T->Right;
  64.         T->Right = G;
  65.         P->Right = T->Left;
  66.         T->Left = P;
  67.         P = GG;
  68.         cofgg = T;
  69.      }
  70.      else { // Do single rotate Right
  71.         G->Left = P->Right;
  72.         P->Right = G;
  73.         cofgg = P;
  74.      }
  75.   }
  76.   else { // G->Right == P
  77.     if (P->Left == T) {  // Do double rotate
  78.        G->Right = T->Left;
  79.        T->Left = G;
  80.        P->Left = T->Right;
  81.        T->Right = P;
  82.        P = GG;
  83.        cofgg = T;
  84.     }
  85.     else { // Do single rotate Left
  86.        G->Right = P->Left;
  87.        P->Left = G;
  88.        cofgg = P;
  89.     }
  90.   }
  91.  
  92.   cofgg->color = BlackNode;
  93.   G->color = RedNode;
  94.  
  95.   if (GG) {
  96.      if (side) GG->Right = cofgg; else GG->Left = cofgg;
  97.   }
  98.   else Root = cofgg;
  99.  
  100.   return Root;
  101. }
  102.  
  103. RBNodeBase *DelBalance(RBNodeBase *Root, PtrPack &pp)
  104. // Balancing code during top down deletion
  105. {
  106.   if ((T == 0 || T->color == BlackNode) && S && S->color == RedNode) {
  107.  
  108.      // Case: T is black, S red. T might be null,
  109.      // but S and P must not be.
  110.  
  111.      // Fix G child to be S. Also S may become P of M
  112.      if (G) {
  113.         if (G->Left == P) G->Left = S; else G->Right = S;
  114.      }
  115.      else Root = S;
  116.      if (P == M) PM = S;
  117.      // Finish rotating
  118.      if (P->Left == T) {
  119.         // RotateLeft(P);
  120.         P->Right = LS;
  121.         S->Left = P;
  122.         G = S;
  123.         S = LS;
  124.      }
  125.      else {
  126.         // RotateRight(P);
  127.         P->Left = RS;
  128.         S->Right = P;
  129.         G = S;
  130.         S = RS;
  131.      }
  132.  
  133.      // Fixup children of S
  134.      if (S) { LS = S->GetLeft(); RS = S->GetRight(); }
  135.      // Fixup colors
  136.      P->color = RedNode; G->color = BlackNode;
  137.   }
  138.  
  139.   if (T && T->color == BlackNode &&
  140.       (T->Left == 0 || T->GetLeft()->color == BlackNode) &&
  141.       (T->Right == 0 || T->GetRight()->color == BlackNode)) {
  142.  
  143.      // Case: T is a single binary node with two black children.
  144.      if (S && S->color == BlackNode &&
  145.          (S->Left == 0 || S->GetLeft()->color == BlackNode) &&
  146.          (S->Right == 0 || S->GetRight()->color == BlackNode)) {
  147.  
  148.        // Case: T and S are single binary nodes with two black children..
  149.        P->color = BlackNode; T->color = RedNode; S->color = RedNode;
  150.  
  151.      }
  152.      else if (LS && LS->color == RedNode) {
  153.  
  154.        // Case: Tree is a single binary node with two black children.
  155.        // S is pair of binary nodes-one red, one black or S is a set
  156.        // of three binary nodes with a black parent and red child nodes.
  157.        // LS is red or RS might be red.
  158.  
  159.        if (P->Left == T) {
  160.           // Fix colors
  161.           LS->color = P->color; P->color = BlackNode; T->color = RedNode;
  162.           // Fix G child to be LS. ALSo LS may become P of M
  163.           if (G) {
  164.              if (G->Left == P) G->Left = LS; else G->Right = LS;
  165.           }
  166.           else Root = LS;
  167.           if (P == M) PM = LS;
  168.           // Finish: DoubleRotateLeft(S, P);
  169.           P->Right = LS->Left;
  170.           LS->Left = P;
  171.           S->Left = LS->Right;
  172.           LS->Right = S;
  173.           G = LS;
  174.           // Do not fix S or LS since they get reassigned
  175.           // at the top of next loop
  176.        }
  177.        else {
  178.           // Fix colors
  179.           S->color = P->color; LS->color = BlackNode;
  180.           P->color = BlackNode; T->color = RedNode;
  181.           // Fix G child to be S. Also S may become P of M
  182.           if (G) {
  183.              if (G->Left == P) G->Left = S; else G->Right = S;
  184.           }
  185.           else Root = S;
  186.           if (P == M) PM = S;
  187.           // Finish: RotateRight(P);
  188.           P->Left = RS;
  189.           S->Right = P;
  190.           G = S;
  191.           // Do not fix S or LS since they get reassigned
  192.           // at the top of next loop
  193.        }
  194.  
  195.      }
  196.      else if (RS && RS->color == RedNode) {
  197.  
  198.        // Case: T is a single binary node with two black children.
  199.        // S is a pair of binary nodes-one red, one black.
  200.        // LS is black, RS is red.   
  201.  
  202.        if (P->Left == T) {
  203.           // Fix colors
  204.           RS->color = BlackNode; S->color = P->color;
  205.           P->color = BlackNode; T->color = RedNode;
  206.           // Fix G child to be S. Also, S may become P of M
  207.           if (G) {
  208.              if (G->Left == P) G->Left = S; else G->Right = S;
  209.           }
  210.           else Root = S;
  211.           if (P == M) PM = S;
  212.           // Finish: RotateLeft(P);
  213.           P->Right = LS;
  214.           S->Left = P;
  215.           G = S;
  216.           // Do not fix S or LS since they get reassigned
  217.           // at the top of next loop
  218.        }
  219.        else {
  220.           // Fix colors
  221.           RS->color = P->color; P->color = BlackNode; T->color = RedNode;
  222.           // Fix G child to become RS. ALSo, RS may become P of M.
  223.           if (G) {
  224.              if (G->Left == P) G->Left = RS; else G->Right = RS;
  225.           }
  226.           else Root = RS;
  227.           if (P == M) PM = RS;
  228.           // Finish: DoubleRotateRight(S, P);
  229.           P->Left = RS->Right;
  230.           RS->Right = P;
  231.           S->Right = RS->Left;
  232.           RS->Left = S;
  233.           G = RS;
  234.           // Do not fix S or LS since they get reassigned
  235.           // at the top of next loop
  236.        }
  237.  
  238.      }
  239.   }
  240.  
  241.   return Root;
  242. }
  243.  
  244. RBNodeBase *DoReplacement(RBNodeBase *Root, PtrPack &pp)
  245. // Swaps the node data in the matching node's successor with the
  246. // node data of the matching node to be deleted. Then the successor
  247. // node with no data is deleted. If the matching node has no successor
  248. // the parent node will equal the matching node and the replacement
  249. // node becomes the non-null child of the matching node.
  250. {
  251.   // At this point, M is the node to delete, PM is it's parent,
  252.   // P is the replacement node, G is it's parent. If M has no
  253.   // successor, P will = M, and replacement is the non-null
  254.   // child of M.
  255.  
  256.   if (M) { // Matching node was found
  257.     if (P == M || M->Left == 0 || M->Right == 0) {
  258.        // No successor, and/or at least one child null
  259.        // Get non-null child, if any, else P will be null
  260.        P = (M->Left) ? M->GetLeft() : M->GetRight();
  261.     }
  262.     else { // M has a successor to use as a replacement
  263.        if (G != M) {
  264.          // Successor is not immediate child of M, so detach
  265.          // from where it is, attach to where M is
  266.          G->Left = P->Right;
  267.          P->Right = M->Right;
  268.        }
  269.        // Finish attaching where M is.
  270.        P->Left = M->Left;
  271.     }
  272.     // P should have same color as M since it's going where M was
  273.     if (P) P->color = M->color;
  274.   }
  275.  
  276.   // Fixup PM child link to be P
  277.   if (M) {
  278.      if (PM) {
  279.         if (PM->Left == M) PM->Left = P; else PM->Right = P;
  280.      }
  281.      else Root = P; // New Root, possibly null
  282.   }
  283.  
  284.   return Root;
  285. }
  286.  
  287. RBNodeBase *DetachMinMax(RBNodeBase *&Root, int mx)
  288. // Detach the smallest node in the tree (the node all the way to the left)
  289. // or the largest node in the tree (the node all the way to the right)
  290. // if mx is true.
  291. {
  292.   struct PtrPack pp;
  293.  
  294.   if (Root == 0) return 0;
  295.  
  296.   T = Root; P = 0; G = 0;
  297.   M = 0; PM = 0;
  298.  
  299.   while (T) {
  300.  
  301.     // Pretend we're on the matching node
  302.     M = T; PM = P;
  303.  
  304.     // Update ancestor pointers
  305.     G = P; P = T;
  306.  
  307.     // Then go all the way Left or Right
  308.     if (mx) {
  309.        T = P->GetRight(); S = P->GetLeft();
  310.     }
  311.     else {
  312.        T = P->GetLeft(); S = P->GetRight();
  313.     }
  314.  
  315.     if (S) {
  316.        LS = S->GetLeft(); RS = S->GetRight();
  317.     }
  318.     else {
  319.        LS = 0; RS = 0;
  320.     }
  321.  
  322.     Root = DelBalance(Root, pp);
  323.  
  324.   } // end of while loop
  325.  
  326.   Root = DoReplacement(Root, pp);
  327.  
  328.   if (Root) Root->color = BlackNode;
  329.  
  330.   return M; // Node to delete
  331. }
  332. // ----------------------------------------------------------- // 
  333. // ------------------------------- //
  334. // --------- End of File --------- //
  335. // ------------------------------- //
  336.